Subset sum “cubes” and the complexity of primality testing

AbstractA Σ32 Boolean circuit has 3 levels of gates. The input level is comprised of OR gates each taking as inputs 2, not necessarily distinct, literals. Each of these ORs feeds one or more AND gates at the second level. Their outputs form the inputs to a single OR gate at the output level. Using the projection technique of Paturi, Saks, and Zane, it is shown that the smallest Σ32 Boolean circuit testing primality for any number given by n binary digits has size 2n−g(n) where g(n)=o(n). Disjunctive normal form (DNF) formulas can be considered to be a special case of Σ32 circuits, and a bound of this sort applies to them too.The argument uses the following number theoretic fact which is established via a modified version of Gallagher's “Larger” Sieve:Let a1<a2<⋯